package exercise48;

/**
 * @Author Fizz Pu
 * @Date 2021/8/9 下午7:29
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词指字母相同，但排列不同的字符串。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 *
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 *
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 *  
 *
 * 提示：
 *
 * 1 <= strs.length <= 104
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/group-anagrams
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.*;

public class Lee49 {
    public static void main(String[] args) {
        System.out.println(new Lee49().groupAnagrams(new String[]{
                "eat", "tea", "tan", "ate", "nat", "bat"
        }));
    }


    // 这题排序加统计
    public List<List<String>> groupAnagrams(String[] strs) {
        // key : str, value : 元素下标
        Map<String, List<Integer>> map = new HashMap<>();

        // 统计
        int index = 0;
        for (String str : strs) {
            String sort = str;
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            sort = String.valueOf(chars);

            List<Integer> list = map.computeIfAbsent(sort, k -> new ArrayList<>());

            list.add(index++);
        }

        // 生成结果
        List<List<String>> ret = new ArrayList<>();

        map.forEach(
                (k, v) -> {
                    List<String> inner = new ArrayList<>();
                    for (int valueIndex : v) {
                        inner.add(strs[valueIndex]);
                    }
                    ret.add(inner);
                }
        );

        return ret;
    }
}
